/*
 * Kodkod -- Copyright (c) 2005-present, Emina Torlak
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
package kodkod.util.ints;

/**
 * A mutable implementation of the <tt>IntVector</tt> interface. Implements all
 * optional IntVector operations. In addition to implementing the
 * <tt>IntVector</tt> interface, this class provides methods to manipulate the
 * size of the array that is used internally to store the elements of the
 * IntVector.
 * <p>
 * The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>, and
 * <tt>iterator</tt> operations run in constant time. The <tt>insert</tt>
 * operations run in <i>amortized constant time</i>, that is, adding n elements
 * requires O(n) time. All of the other operations run in linear time (roughly
 * speaking).
 * <p>
 * Each <tt>MutableIntVector</tt> instance has a <i>capacity</i>. The capacity
 * is the size of the array used to store the elements in the list. It is always
 * at least as large as the list size. As elements are added to a
 * MutableIntVector, its capacity grows automatically. The details of the growth
 * policy are not specified beyond the fact that adding an element has constant
 * amortized time cost.
 * <p>
 * An application can increase the capacity of an <tt>MutableIntVector</tt>
 * instance before adding a large number of elements using the
 * <tt>ensureCapacity</tt> operation. This may reduce the amount of incremental
 * reallocation.
 * <p>
 * This impementation is not synchronized and its iterators are not fail-fast.
 *
 * @author Emina Torlak
 */
public final class ArrayIntVector extends AbstractIntVector {

    private int[] elements;
    private int   size;

    /**
     * Constructs an empty <tt>MutableIntVector</tt> with the specified initial
     * capacity.
     *
     * @exception IllegalArgumentException if the specified initial capacity is
     *                negative
     */
    public ArrayIntVector(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        this.elements = new int[initialCapacity];
    }

    /**
     * Constructs an empty <tt>MutableIntVector</tt> with an initial capacity of
     * ten.
     */
    public ArrayIntVector() {
        this(10);
    }

    /**
     * Constructs a <tt>MutableIntVector</tt> containing the elements of the
     * specified array, in proper sequence. The <tt>MutableIntVector</tt> instance
     * has an initial capacity of 110% the size of the specified collection.
     *
     * @throws NullPointerException if the specified array is null.
     */
    public ArrayIntVector(int[] array) {
        size = array.length;
        // Allow 10% room for growth
        int capacity = (int) Math.min((size * 110L) / 100, Integer.MAX_VALUE);
        elements = new int[capacity];
        System.arraycopy(array, 0, elements, 0, size);
    }

    /**
     * Trims the capacity of this <tt>MutableIntVector</tt> instance to be the
     * list's current size. An application can use this operation to minimize the
     * storage of an <tt>MutableIntVector</tt> instance.
     */
    public void trimToSize() {

        int oldCapacity = elements.length;
        if (size < oldCapacity) {
            int[] oldData = elements;
            elements = new int[size];
            System.arraycopy(oldData, 0, elements, 0, size);
        }
    }

    /**
     * Increases the capacity of this <tt>MutableIntVector</tt> instance, if
     * necessary, to ensure that it can hold at least the number of elements
     * specified by the minimum capacity argument.
     */
    public void ensureCapacity(int minCapacity) {

        int oldCapacity = elements.length;
        if (minCapacity > oldCapacity) {
            int[] oldData = elements;
            int newCapacity = (oldCapacity * 3) / 2 + 1;
            if (newCapacity < minCapacity)
                newCapacity = minCapacity;
            elements = new int[newCapacity];
            System.arraycopy(oldData, 0, elements, 0, size);
        }
    }

    /**
     * @throws IndexOutOfBoundsException index < 0 or index >= size
     */
    private void checkExcludeLength(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException();
    }

    /**
     * @throws IndexOutOfBoundsException index < 0 or index > size
     */
    private void checkIncludeLength(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException();
    }

    /**
     * {@inheritDoc}
     *
     * @see kodkod.util.ints.IntVector#get(int)
     */
    @Override
    public int get(int index) {
        checkExcludeLength(index);
        return elements[index];
    }

    /**
     * {@inheritDoc}
     *
     * @see kodkod.util.ints.IntVector#size()
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * {@inheritDoc}
     *
     * @see kodkod.util.ints.IntVector#set(int, int)
     */
    @Override
    public int set(int index, int element) {
        final int oldValue = get(index);
        elements[index] = element;
        return oldValue;
    }

    /**
     * {@inheritDoc}
     *
     * @see kodkod.util.ints.IntVector#add(int)
     */
    @Override
    public boolean add(int element) {
        ensureCapacity(size + 1);
        elements[size++] = element;
        return true;
    }

    /**
     * {@inheritDoc}
     *
     * @see kodkod.util.ints.IntVector#add(int, int)
     */
    @Override
    public void add(int index, int element) {
        checkIncludeLength(index);

        ensureCapacity(size + 1);
        System.arraycopy(elements, index, elements, index + 1, size - index);
        elements[index] = element;
        size++;
    }

    /**
     * {@inheritDoc}
     *
     * @see kodkod.util.ints.IntVector#addAll(int, kodkod.util.ints.IntCollection)
     */
    @Override
    public boolean addAll(int index, IntCollection c) {
        checkIncludeLength(index);

        final int csize = c.size();
        if (csize == 0)
            return false;

        ensureCapacity(size + csize);
        System.arraycopy(elements, index, elements, index + csize, size - index);

        for (IntIterator iter = c.iterator(); iter.hasNext();) {
            elements[index++] = iter.next();
        }

        return true;
    }

    /**
     * {@inheritDoc}
     *
     * @see kodkod.util.ints.AbstractIntVector#removeAt(int)
     */
    @Override
    public int removeAt(int index) {
        checkExcludeLength(index);
        final int old = elements[index];
        System.arraycopy(elements, index + 1, elements, index, size - index - 1);
        size--;
        return old;
    }

    /**
     * {@inheritDoc}
     *
     * @see kodkod.util.ints.AbstractIntCollection#toArray(int[])
     */
    @Override
    public int[] toArray(int[] array) {
        if (array.length < size) {
            array = new int[size];
        }
        System.arraycopy(elements, 0, array, 0, size);
        return array;
    }
}
